package com.wzp.algorithm.common;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class Prelude {

    public static boolean validPalindrome(String s) {
        int i = -1, j = s.length();
        while (++i <= --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
            }
        }
        return true;
    }

    private static boolean isPalindrome(String s, int i, int j) {
        while (i <= j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
//        topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);
//        topKFrequent(new int[]{1}, 1);
//        System.out.println(sortColors(new int[]{2, 0, 1}));
//        System.out.println(Arrays.toString(sortColors(new int[]{1, 2, 0})));
//        System.out.println(isSubsequence("abc", "ahbgdc"));
//        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
//        System.out.println(wordPattern("aabb", "北京 杭州 杭州 北京"));
//        System.out.println(wordPattern("aabb", "北京 北京 杭州 杭州"));
        ReentrantLock reentrantLock = new ReentrantLock();
        ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(20);
        PriorityQueue<Object> priorityQueue = new PriorityQueue<>();
        HashMap<Object, Object> hashMap = new HashMap<>();
        ConcurrentHashMap<Object, Object> concurrentHashMap = new ConcurrentHashMap<>();
        StringBuffer stringBuffer = new StringBuffer();
        StringBuilder stringBuilder = new StringBuilder();
        ThreadLocal<Object> threadLocal = new ThreadLocal<>();
        threadLocal.set(1);

        System.out.println((4 - 1) & 118);
//        System.out.println((8 - 1) & 118);
//        System.out.println((16 - 1) & 118);
//        System.out.println((32 - 1) & 118);
        System.out.println((64 - 1) & 118);
        System.out.println((128 - 1) & 118);

//        118:0111 0110
//        4-1:0000 0011
//          2:0000 0010

//        118:0111 0110
//       64-1:0011 1111
//         54:0011 0110

//        118:0111 0110
//      128-1:0111 1111
//        118:0111 0110


//          2:0000 0010
//            0111 0100
//        118:0111 0110

    }

    public static boolean wordPattern(String pattern, String str) {
        if (pattern == null || str == null || str.isEmpty()) {
            return false;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();

        String[] strings = str.split(" ");

        for (int i = 0; i < strings.length; i++) {
            Integer m1 = map1.put(pattern.charAt(i), i);
            Integer m2 = map2.put(strings[i], i);
            System.out.println("m1=" + m1 + ",m2=" + m2);
            if ((m1 != null || m2 != null) &&  !m1.equals(m2)){
                return false;
            }
        }
        return true;
    }

    public static int maxProfit(int[] prices) {
        // 1 ms	38.2 MB
        // if (prices == null || prices.length <= 1) return 0;
        // int ans = 0;
        // for (int i = 1; i < prices.length; i++) {
        //     if (prices[i] > prices[i-1]) {  // 卖出有利可图
        //         ans += (prices[i] - prices[i-1]);
        //     }
        // }
        // return ans;

        // 贪心算法 1 ms    38.4 MB
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;

        // 动态规划 2 ms	38.5 MB
//        int n = prices.length;
//        int dp0 = 0, dp1 = -prices[0];
//        for (int i = 1; i < n; ++i) {
//            int newDp0 = Math.max(dp0, dp1 + prices[i]);
//            int newDp1 = Math.max(dp1, dp0 - prices[i]);
//            dp0 = newDp0;
//            dp1 = newDp1;
//        }
//        return dp0;

    }


    public static boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            index = t.indexOf(c, index + 1);
            if (index == -1) {
                return false;
            }
        }
        return true;
    }

    public static int[] sortColors(int[] nums) {
        int zero = 0, one = 0, two = nums.length - 1;
        while (one <= two) {
            if (nums[one] == 0) {
                swap(nums, zero++, one++);
            } else if (nums[one] == 2) {
                swap(nums, one, two--);
            } else {
                one++;
            }
        }
        return nums;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1, index2 = n - 1;
        int mergeIndex = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                nums1[mergeIndex--] = nums2[index2--];
            } else if (index2 < 0) {
                nums1[mergeIndex--] = nums1[index1--];
            } else if (nums1[index1] > nums2[index2]) {
                nums1[mergeIndex--] = nums1[index1--];
            } else {
                nums1[mergeIndex--] = nums2[index2--];
            }
        }
        System.out.println(Arrays.toString(nums1));
    }

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int num : nums) {
            numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        // Integer:数组元素出现次数 -> List<Integer> nums
        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        for (int key : numMap.keySet()) {
            int cost = numMap.get(key);
            if (buckets[cost] == null) {
                buckets[cost] = new ArrayList<>();
            }
            buckets[cost].add(key);
        }
        int[] topK = new int[k];
        int index = 0;
        for (int i = buckets.length - 1; i >= 0 && index < k; i--) {
            List<Integer> bucket = buckets[i];
            if (bucket == null) continue;
            for (int num : bucket) {
                topK[index++] = num;
            }
        }
        return topK;
    }


}
